using System;
using System.Collections.Generic;
using System.Text;

namespace CrossRiver
{
    public struct State
    {
        public int boatlocation;
        public int nPeople;
        public int nIndians;
        
    };

    public struct Tree
    {
        public State currentState;
        public List<Tree> list;

        public List<State> formerStates;
    };

    class Process
    {
        public bool AddState(List<State> list, int boatlocation, int nMissionary, int nCannibal)
        {
            State state;
            state.boatlocation = boatlocation;
            state.nPeople = nMissionary;
            state.nIndians = nCannibal;
            list.Add(state);
            return true;
        }

        public bool TerminalCheck(State state)
        {
            bool bReturn = false;

            // The final end check.
            if( ( 1 == state.boatlocation ) &&
                ( 0 == state.nPeople) &&
                ( 0 == state.nIndians)
              )
            {
                bReturn = false;
                return bReturn;
            }

            bReturn = true;
            return bReturn;
        }

        public bool CompareTwoState(Tree currentTree, State possibleState)
        {
            bool bReturn = false;

            // Terminal check.
            // If the currentTree is the end condition. Then end it.
            bReturn = TerminalCheck(currentTree.currentState);
            if (false == bReturn)
            {
                return false;
            }

            // Sequence Limit.
            bReturn = CompareSquenceLimit(currentTree.currentState, possibleState);
            if (false == bReturn)
            {
                return false;
            }

            // Capacity Limit.
            bReturn = CompareCapacityLimit(currentTree.currentState, possibleState);
            if (false == bReturn)
            {
                return false;
            }

            // CompareRepeat.
            bReturn = CompareRepeat(currentTree.formerStates, possibleState);
            if (false == bReturn)
            {
                return false;
            }



            bReturn = true;
            return bReturn;
        }

        public bool CompareRepeat(List<State> fatherSequences, State possible)
        {
            bool bReturn = false;

            bool bisIn = fatherSequences.Contains(possible);

            // If the possible state is not in the fatherSequences, we consider it's right.
            bReturn = !bisIn;

            return bReturn;
        }

        public bool CompareCapacityLimit(State current, State possible)
        {
            bool bReturn = false;

            if (0 == current.boatlocation)
            {
                // Decrease.
                if (current.nPeople < possible.nPeople)
                {
                    return false;
                }
                if (current.nIndians < possible.nIndians)
                {
                    return false;
                }

                int total = 0;
                total = Math.Abs(current.nPeople - possible.nPeople) +
                        Math.Abs(current.nIndians - possible.nIndians);

                if ((0 == total) || (total > 2))
                {
                    return false;
                }
            }
            else
            {
                // Increase.
                if (current.nPeople > possible.nPeople)
                {
                    return false;
                }
                if (current.nIndians > possible.nIndians)
                {
                    return false;
                }

                int total = 0;
                total = Math.Abs(possible.nPeople - current.nPeople) +
                        Math.Abs(possible.nIndians - current.nIndians);

                if ((0 == total) || (total > 2))
                {
                    return false;
                }
            }

            bReturn = true;

            return bReturn;
        }

        public bool CompareSquenceLimit(State current, State possible)
        {
            bool bReturn = false;

            if (current.boatlocation != possible.boatlocation)
            {
                bReturn = true;
            }

            return bReturn;
        }

        // Add suitableState to current tree.
        public bool AddSuitableTree(Tree tree, List<State> available)
        {
            
            foreach (State state in available)
            {
                // CompareTwoState
                bool bCompare = false;
                bCompare = CompareTwoState(tree, state);

                if (true == bCompare)
                {
                    // Build a new tree.
                    Tree subTree;
                    subTree.currentState = state;
                    subTree.list = new List<Tree>();
                    subTree.formerStates = new List<State>();

                    // Add this subTree to last Tree.
                    tree.list.Add(subTree);

                    // Add this sequence of father sequence.
                    AddSquences(subTree.formerStates, tree.formerStates);

                    // Add this state.
                    subTree.formerStates.Add(subTree.currentState);
                }
                else
                {
                    // do nothing.
                }

            }


            return true;
        }

        public bool AddSquences(List<State> sonSequence, List<State> fatherSquence)
        {
            for (int i = 0; i < fatherSquence.Count; i++)
            {
                sonSequence.Add(fatherSquence[i]);
            }

            return false;
        }

        public bool Generate(Tree tree, List<State> available)
        {
 
            // Add suitable to the current tree.
            AddSuitableTree(tree, available);

            // According to the new tree, and new subtree.
            foreach (Tree subTree in tree.list)
            {
                Generate(subTree, available);
            }


            return true;
        }

        public bool Run()
        {
            //Console.WriteLine("Hello World!");

            //MyState a;
            //a.boatlocation = 0;
            //a.nCannibal = 3;
            //a.nMissionary = 3;

            //MyTree mainTree;
            //mainTree.currentState = a;

            //Console.WriteLine("({0}, {1}, {2})",
            //                    mainTree.currentState.boatlocation,
            //                    mainTree.currentState.nCannibal,
            //                    mainTree.currentState.nMissionary);



            // Initialization the available states.
            List<State> availble;
            availble = new List<State>();

            AddState(availble, 0, 0, 1);
            AddState(availble, 0, 0, 2);
            AddState(availble, 0, 0, 3);
            AddState(availble, 0, 1, 1);
            AddState(availble, 0, 2, 2);
            AddState(availble, 0, 3, 0);
            AddState(availble, 0, 3, 1);
            AddState(availble, 0, 3, 2);
            AddState(availble, 0, 3, 3);
            AddState(availble, 1, 0, 1);
            AddState(availble, 1, 0, 2);
            AddState(availble, 1, 0, 3);
            AddState(availble, 1, 1, 1);
            AddState(availble, 1, 2, 2);
            AddState(availble, 1, 3, 0);
            AddState(availble, 1, 3, 1);
            AddState(availble, 1, 3, 2);
            AddState(availble, 1, 0, 0);

            // Create the whole tree.
            Tree wholeTree;
            wholeTree.currentState.boatlocation = 0;
            wholeTree.currentState.nPeople = 3;
            wholeTree.currentState.nIndians = 3;
            wholeTree.list = new List<Tree>();
            wholeTree.formerStates = new List<State>();
            wholeTree.formerStates.Add(wholeTree.currentState);

            Generate(wholeTree, availble);

            // Find the shortest tree.
            State endState = new State();
            endState.boatlocation   = 1;
            endState.nPeople    = 0;
            endState.nIndians      = 0;

            Find(wholeTree, endState);

            // Show the result.

            return true;
        }

        public bool Find(Tree tree, State endState)
        {
            bool bCheck = false;

            bCheck = tree.formerStates.Contains(endState);

            if( true == bCheck )
            {
                // Display.
                int numShow = tree.formerStates.Count;

                for( int i = 0; i < numShow; i++ )
                {
                    Console.Write("({0},{1},{2})",
                                  tree.formerStates[i].boatlocation,
                                  tree.formerStates[i].nPeople,
                                  tree.formerStates[i].nIndians);
                }

                Console.WriteLine();
                Console.WriteLine();
  
            }
            else
            {
                // Input all subTree.
                int num = tree.list.Count;
                for( int i = 0; i < num; i++ )
                {
                    Find(tree.list[i], endState);
                }
            }

            return false;
        }
    }
}
